package com.heima.leetcode.practice;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 4 寻找两个有序数组的中位数
 * @date 2024/11/26 10:52
 */
public class E4 {

    /**
     * <h3>方法一，合并，O(M+N)</h3>
     *
     * @param nums1 数组1
     * @param nums2 数组2
     * @return 中位数
     */
    public double findMedianSortedArrays1(int[] nums1, int[] nums2) {
        int[] merge = new int[nums1.length + nums2.length];
        int index1 = 0, index2 = 0, index = 0;
        // 合并有序数组
        while (index1 < nums1.length && index2 < nums2.length) {
            if (nums1[index1] < nums2[index2]) {
                merge[index++] = nums1[index1++];
            } else {
                merge[index++] = nums2[index2++];
            }
        }
        if (index1 < nums1.length) {
            while (index < merge.length) {
                merge[index++] = nums1[index1++];
            }
        }
        if (index2 < nums2.length) {
            while (index < merge.length) {
                merge[index++] = nums2[index2++];
            }
        }
        if ((merge.length & 1) == 1) {
            return merge[merge.length >> 1];
        } else {
            int left = merge[merge.length >> 1]; // 直接除是后面一个
            int right = merge[(merge.length >> 1) - 1];
            return (left + right) / 2.0;
        }
    }

    /**
     * <h3>方法二，合并，优化代码O(M+N)</h3>
     *
     * @param nums1 数组1
     * @param nums2 数组2
     * @return 中位数
     */
    public double findMedianSortedArrays2(int[] nums1, int[] nums2) {
        int[] merge = new int[nums1.length + nums2.length];
        int index1 = 0, index2 = 0, index = 0;
        // 合并有序数组
        while (index1 < nums1.length && index2 < nums2.length) {
            if (nums1[index1] < nums2[index2]) {
                merge[index++] = nums1[index1++];
            } else {
                merge[index++] = nums2[index2++];
            }
        }
        while (index1 < nums1.length) {
            merge[index++] = nums1[index1++];
        }
        while (index2 < nums2.length) {
            merge[index++] = nums2[index2++];
        }
        if ((merge.length & 1) == 1) {
            return merge[merge.length >> 1];
        } else {
            int left = merge[merge.length >> 1]; // 直接除是后面一个
            int right = merge[(merge.length >> 1) - 1];
            return (left + right) / 2.0;
        }
    }

    /**
     * <h3>方法三，合并，优化代码，不用真的全部合并，可以提前结束O(M+N)，最推荐</h3>
     *
     * @param nums1 数组1
     * @param nums2 数组2
     * @return 中位数
     */
    public double findMedianSortedArrays3(int[] nums1, int[] nums2) {
        int length = nums1.length + nums2.length; // 总长度
        int medianIndex = length >> 1; // 中位数可能下标
        int index1 = 0, index2 = 0; // 两个数组指针
        int prev = 0, curr = 0; // 中位数和它前一个数
        for (int index = 0; index <= medianIndex; index++) { // 最终curr落在medianIndex索引位置处
            prev = curr;
            // 选nums1的元素作为当前位置的数
            if (index1 < nums1.length && (index2 >= nums2.length || nums1[index1] < nums2[index2])) {
                curr = nums1[index1++];
            }
            // 选nums2的元素作为当前位置的数
            else {
                curr = nums2[index2++];
            }
        }
        if ((length & 1) == 1) {
            return curr;
        } else {
            return (prev + curr) / 2.0;
        }
    }

    /**
     * <h3>方法四，合并，优化代码，不用真的全部合并，可以提前结束O(M+N)，和方法三一模一样</h3>
     *
     * @param nums1 数组1
     * @param nums2 数组2
     * @return 中位数
     */
    public double findMedianSortedArrays4(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        boolean odd = ((m + n) & 1) == 1;
        int median = (m + n) >> 1;
        int index1 = 0, index2 = 0, leftNum = 0, rightNum = 0;
        for (int i = 0; i <= median; i++) {
            if (index2 >= nums2.length ||
                    (index1 < nums1.length && nums1[index1] < nums2[index2])) {
                if (i == median - 1) {
                    leftNum = nums1[index1];
                } else if (i == median) {
                    rightNum = nums1[index1];
                    break;
                }
                index1++;
            } else {
                if (i == median - 1) {
                    leftNum = nums2[index2];
                } else if (i == median) {
                    rightNum = nums2[index2];
                    break;
                }
                index2++;
            }
        }
        return odd ? rightNum : (leftNum + rightNum) / 2.0;
    }
}
